#include <iostream>
#include <list>
#include <pthread.h>
#include <vector>
#include <unistd.h>
#include <mutex>
struct memory
{
        memory(int start,int size) : _start(start),_size(size){}
        int _start;//起始位置
        int _size;//大小
};
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;
class memory_manager
{
    public:
    //把一个大的内存块划分为两个小的内存块
    memory split_apart(std::list<memory>::iterator it,int size)
    {
        Print();
        //1、构建出要返回的内存块，以大内存的开头作为起点，size作为大小       
        memory ret(it->_start,size);
        //2、计算经过分割的大内存块的新起始地址
        int newStart = it->_start + size;
        //3、修改大内存块的起始地址与大小
        it->_size = it->_size - size;
        it->_start = newStart;
        if(it->_size == 0) _unused_block.erase(it);
        return ret;
        Print();
    }
    //进程用完该内存后，合并内存块
    void split_merge(memory m)
    {
        bool is = false; //is标志位用于判断是否发生了合并
        auto iter = _unused_block.begin();
        std::list<memory>::iterator merge_node;
        while(iter != _unused_block.end())
        {
            //查看合并内存块的起点是否可以合并
            if(iter->_start + iter->_size == m._start)
            {
                //可以合并
                is = true;
                merge_node = iter;
                iter->_size += m._size;
            }
            //查看合并内存块的终点是否可以合并
            if(!is && iter->_start == m._start + m._size)
            {
                //可以合并
                is = true;
                merge_node = iter;
                iter->_start = m._start;
                iter->_size += m._size;
            }
            ++iter;
        }
        //如果该内存块未发生合并，则在空闲表中为该内存块新插入一个节点
        if(!is)
        {
            _unused_block.push_back(m);
        }
        else
        {
            //发生合并，空闲表中可能还可以合并
            _unused_block.erase(merge_node);
            split_merge(*merge_node);
        }
        Print();
    }
    public:
    //传入一个大的内存块用于初始化
    void Print()
    {
        std::cout << "-----------------" << std::endl;
        std::cout << "空闲内存块情况："<<std::endl;
        for(auto& iter : _unused_block)
        {
            std::cout << iter._start << ":" << iter._size << " ";
        }

    }
    memory_manager(memory m){ _unused_block.push_back(m); }
    bool memory_request_first_fit(int size,memory& m) //进程请求内存函数——最先适应算法
    {
        auto iter = _unused_block.begin();
        while(iter != _unused_block.end())
        {
            if(iter->_size >= size)
            {
              m = split_apart(iter,size);
              //本次内存请求成功，返回true
              return true;
            }
            ++iter;
        }
        //本次内存请求失败，返回false
        return false;
    }
    
    
    bool memory_recycle(memory m)
    {
        split_merge(m);
        return true;
    }
    private:
    //元素存储每个内存块的起始位置和结束位置 
        std::list<memory> _unused_block; //闲置内存块
};
struct pthread_data
{
    pthread_data(const std::string& threadname, memory_manager* mm,
    int run_time,int run_size)
    :_threadname(threadname),_mm(mm),_m(0,0),_run_time(run_time),_run_size(run_size)
    {}
    std::string _threadname; //线程名
    memory _m;// 线程申请成功的内存块
    pthread_t _tid; //线程标识符
    int _run_time; //线程执行任务的时长
    int _run_size; //线程执行任务所需内存空间大小
    memory_manager* _mm; //内存管理操作句柄
};
void* thread_run(void* arg)
{
    pthread_data* data = static_cast<pthread_data*>(arg);
    int cnt = 2;
    while(cnt)
    {
        cnt--;
        memory_manager* mm = data->_mm;
        pthread_mutex_lock(&mutex1);
        bool ret;
        do
        {
            ret = mm->memory_request_first_fit(data->_run_size,data->_m);
            if(ret == false) 
            {
                std::cout << "目前内存不够，请稍后再试" << std::endl;
                sleep(1);
            }
        }while(!ret);
        printf("线程名:%s,申请空间大小:%d成功！，执行任务时长:%dms\n",data->_threadname.c_str(),data->_run_size,data->_run_time);
        //执行完得释放内存块
        mm->memory_recycle(data->_m);
        data->_mm->Print();
        pthread_mutex_unlock(&mutex1);
        usleep(data->_run_time*1000);
        printf("线程:%s 执行结束，归还空间大小:%d\n",data->_threadname.c_str(),data->_run_size);
    }

    
}
int main()
{
    memory_manager mm({0,4096});
    //模拟五个线程，申请内存块，用usleep模拟进程运行时间
    std::vector<pthread_data> threads;
    for(int i = 1 ; i <= 2 ; ++i)
    {
        threads.emplace_back("thread"+ std::to_string(i),&mm,i*1000,i*1100);
    }
    for(auto& thread : threads)
    {
        usleep(1000);
        pthread_create(&thread._tid,nullptr,thread_run,static_cast<void*>(&thread));
    }
    for(auto& thread : threads)
    {
        pthread_join(thread._tid,nullptr);
    }
    return 0;
}